package leetcode.code1249;

import java.util.Stack;

public class Solution {
	public String minRemoveToMakeValid(String s) {
		char[] cs = s.toCharArray();
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < s.length(); i++) {
			char c = cs[i];
			if (c == '(') {
				stack.add(i);
			} else if (c == ')') {
				if (stack.isEmpty()) {
					cs[i] = '1';
				} else {
					stack.pop();
				}
			}
		}
		while (!stack.isEmpty()) {
			cs[stack.pop()] = '1';
		}
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < cs.length; i++) {
			if (cs[i] != '1') {
				sb.append(cs[i]);
			}
		}
		return sb.toString();
	}
}
